package main

import (
	"fmt"
	"math"
	"time"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		// fmt.Println("return")
		return nil
	}
	result := [][]int{{root.Val}}

	// count := 0
	// fmt.Println(result)

	left := levelOrder(root.Left)
	right := levelOrder(root.Right)
	// fmt.Println(len(left), len(right))
	// if len(left) > len(right) {
	// 	count = len(left)
	// } else {
	// 	count = len(right)
	// }
	count := (int)(math.Max(float64(len(left)), float64(len(right))))
	// fmt.Println(count)
	// fmt.Println(result, left, right)

	for i := 0; i < count; i++ {
		array := []int{}
		if i < len(left) {
			// fmt.Println(left[i])
			array = append(array, left[i]...)
		}
		if i < len(right) {
			// fmt.Println(right[i])
			array = append(array, right[i]...)
		}
		// fmt.Println(array)
		result = append(result, array)
		// fmt.Println(array, result)
		// array = append(array[0:0])
		// fmt.Println(array)
	}
	// fmt.Println(result)
	// fmt.Println()
	return result
}

func main() {
	start := time.Now()
	root := TreeNode{3, nil, nil}
	leaf1 := TreeNode{9, nil, nil}
	leaf2 := TreeNode{20, nil, nil}
	leaf3 := TreeNode{15, nil, nil}
	leaf4 := TreeNode{7, nil, nil}

	root.Left = &leaf1
	root.Right = &leaf2
	leaf2.Left = &leaf3
	leaf2.Right = &leaf4

	dec := levelOrder(&root)
	cost := time.Since(start)
	fmt.Println(dec)
	fmt.Println(cost)
}
